package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * 有 2 7 3 5 3 1 10 12 …… 不同面值的硬币，求解已最少的硬币数凑齐 15元
 */
@Slf4j
public class Code02_MinCountCoin {
    /**
     * @param arr 硬币
     * @param aim 目标金额
     * @return
     */
    public static int minCount1(int[] arr, int aim) {
        int index = 0;
        int pre = 0;
        return minCount1(arr, aim, index, pre);
    }

    /**
     * 求解已最少的硬币数凑齐
     *
     * @param arr   硬币数组
     * @param aim   目标金额
     * @param index 从index 以及之后的硬币任选
     * @param pre   之前以及累积了多少硬币金额
     * @return
     */
    private static int minCount1(int[] arr, int aim, int index, int pre) {
        if (aim == pre) {
            return 0;
        }
        if (aim < pre) {
            return -1; // 无效解
        }
        if (index >= arr.length) {
            return -1;
        }

        int choose = minCount1(arr, aim, index + 1, pre + arr[index]);
        int noChoose = minCount1(arr, aim, index + 1, pre);

        if (choose == -1 && noChoose == -1) {
            return -1;
        } else if (choose == -1) {
            return noChoose;
        } else if (noChoose == -1) {
            return choose + 1;
        } else {
            return Math.min(choose + 1, noChoose);
        }
    }

    /*
     * 记忆搜索dp
     * index: 0~arr.length
     * pre : 0~aim
     * */
    public static int minCount2(int[] arr, int aim) {
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = -2;
            }
        }
        return minCount2(arr, aim, 0, 0, dp);
    }

    private static int minCount2(int[] arr, int aim, int index, int pre, int[][] dp) {
        if (dp[index][pre] != -2) {
            return dp[index][pre];
        }

        if (aim == pre) {
            dp[index][pre] = 0;
            return 0;
        }
        if (aim < pre) {
            dp[index][pre] = -1;
            return -1; // 无效解
        }
        if (index >= arr.length) {
            dp[index][pre] = -1;
            return -1;
        }

        int choose = minCount1(arr, aim, index + 1, pre + arr[index]);
        int noChoose = minCount1(arr, aim, index + 1, pre);

        if (choose == -1 && noChoose == -1) {
            dp[index][pre] = -1;
        } else if (choose == -1) {
            dp[index][pre] = noChoose;
        } else if (noChoose == -1) {
            dp[index][pre] = choose + 1;
        } else {
            dp[index][pre] = Math.min(choose + 1, noChoose);
        }
        return dp[index][pre];
    }

    /*
     * 严格表结构dp
     *
     * index: 0~arr.length
     * pre : 0~aim
     * */
    public static int minCount3(int[] arr, int aim) {
        return minCount3(arr, aim, 0, 0);
    }


    private static int minCount3(int[] arr, int aim, int initIndex, int initPre) {
        // index pre
        int[][] dp = new int[arr.length + 1][aim + 1];
        // 注意初始化先后顺序
        for (int pre = 0; pre <= aim; pre++) {
            dp[arr.length][pre] = -1;
        }
        for (int index = 0; index < arr.length + 1; index++) {
            dp[index][aim] = 0;
        }

        for (int index = arr.length - 1; index >= initIndex; index--) {
            for (int pre = 0; pre <= aim; pre++) {
                int choose = pre + arr[index] <= aim ? dp[index + 1][pre + arr[index]] : -1;
                int noChoose = dp[index + 1][pre];
                if (choose == -1 && noChoose == -1) {
                    dp[index][pre] = -1;
                } else if (choose == -1) {
                    dp[index][pre] = noChoose;
                } else if (noChoose == -1) {
                    dp[index][pre] = choose + 1;
                } else {
                    dp[index][pre] = Math.min(choose + 1, noChoose);
                }
            }
        }
        return dp[initIndex][initPre];
    }


    public static void main(String[] args) {
        int[] arr = {2, 23, 4, 65, 12, 4, 43, 7, 3, 8, 2, 90};
        int aim = 50; // result = 2
        log.info("暴力递归，计算结果: {}", minCount1(arr, aim));
        log.info("记忆搜索DP，计算结果: {}", minCount2(arr, aim));
        log.info("严格表结构DP，计算结果: {}", minCount3(arr, aim));
    }
}
